/**
 * 1379. 找出克隆二叉树中的相同节点
 * https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/
 */
public class Solutions_1379 {
    public static void main(String[] args) {
        TreeNode original = new TreeNode(7);
        TreeNode target = new TreeNode(3);
        original.left = new TreeNode(4);
        original.right = target;
        original.right.left = new TreeNode(6);
        original.right.right = new TreeNode(19);

        TreeNode cloned = original;  // output: 3
        TreeNode result = getTargetCopy(original, cloned, target);
        System.out.println(result);
    }

    public static final TreeNode getTargetCopy(final TreeNode original,
                                        final TreeNode cloned,
                                        final TreeNode target) {
        if (original == null || original == target) {
            // 返回 cloned 上的对象
            return cloned;
        }
        // original 与 cloned 同时递归，保证两个树的取值结构相同
        TreeNode leftRes = getTargetCopy(original.left, cloned.left, target);
        if (leftRes != null) {
            return leftRes;
        }
        TreeNode rightRes = getTargetCopy(original.right, cloned.right, target);
        if (rightRes != null) {
            return rightRes;
        }
        return null;
    }
}
